import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wangxin
 * Date: 2024-11-18
 * Time: 18:11
 */

   class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }

public class test1 {
       //第一种解法
    public boolean findTreeNode(TreeNode root, int target,List<Integer> list){
        if(root == null){
            return false;
        }
        if(root.val == target){
            list.add(root.val);
            return true;
        }
        boolean f1 = findTreeNode(root.left,target,list);
        boolean f2 = findTreeNode(root.right,target,list);
        if(f1 == true||f2 == true){
            list.add(root.val);
            return true;
        }
        return false;
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        findTreeNode(root,o1,list1);
        findTreeNode(root,o2,list2);
        int i = list1.size() - 1;
        int j = list2.size() - 1;
        while(i >= 0&&j>=0){
            int t1 = list1.get(i);
            int t2 = list2.get(j);
            if(t1 != t2){
                return list1.get(i+1);
            }
            i--;
            j--;
        }
        if(i < 0){
            return list1.get(0);
        }
        if (j < 0){
            return list2.get(0);
        }
        return -1;
    }
//第二种解法
    public TreeNode helper(TreeNode root, int o1, int o2){
        if(root == null||root.val == o1||root.val == o2){
            return root;
        }
        TreeNode left = helper(root.left,o1,o2);
        TreeNode right = helper(root.right,o1,o2);
        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }
        return root;
    }
    public int lowestCommonAncestor2 (TreeNode root, int o1, int o2) {
        // write code here

        return helper(root,o1,o2).val;
    }
//测试代码
//    public static void main(String[] args) {
//        TreeNode root = new TreeNode(3) ; //{3,5,1,6,2,0,8,#,#,7,4},5,1
//        TreeNode r2 = new TreeNode(5) ;
//        TreeNode r3 = new TreeNode(1) ;
//        TreeNode r4 = new TreeNode(6) ;
//        TreeNode r5 = new TreeNode(2) ;
//        TreeNode r6 = new TreeNode(0) ;
//        TreeNode r7 = new TreeNode(8) ;
//        TreeNode r8 = new TreeNode(7) ;
//        TreeNode r9 = new TreeNode(4) ;
//        root.left = r2;
//        root.right = r3;
//        r2.left = r4;
//        r2.right = r5;
//        r3.left = r6;
//        r3.right = r7;
//        r5.left = r8;
//        r5.right = r9;
//        List<Integer> list1 = new ArrayList<>();
//        List<Integer> list2 = new ArrayList<>();
//        findTreeNode(root,7,list1);
//        findTreeNode(root,2,list2);
//        int i = list1.size() - 1;
//        int j = list2.size() - 1;
//        while(i > 0&&j>0){
//            int t1 = list1.get(i);
//            int t2 = list2.get(j);
//            if(t1 != t2){
//                System.out.println(list1.get(i+1));
//                return;
//            }
//            i--;
//            j--;
//        }
//        if(i < 0){
//            System.out.println(list1.get(0));
//        }
//        if (j < 0){
//            System.out.println(list2.get(0));
//        }
//    }
}
